package cn.zjitc.algorithm.sort;

public class Merge {
    private static Comparable[] assist;

    private static boolean less(Comparable x,Comparable y){
        return x.compareTo(y)<0;
    }
    private static void exch(Comparable[]a,int i ,int j){
        Comparable temp=a[i];
        a[i]=a[j];
        a[j]=temp;
    }
    public static void sort(Comparable[] a){
        //初始化辅助数组assist
        assist=new Comparable[a.length];
        //定义一个lo变量和一个hi变量，分别记录数组中最小的索引和最大的索引
        int lo=0;
        int hi=a.length-1;
        //调用sort重载方法完成数组a中，从索引lo到索引hi的元素的排序
        sort(a,lo,hi);
    }
    private static void sort(Comparable[]a,int lo,int hi){
        //安全性校验
        if(hi<=lo){
            return;
        }
        //对数据lo到hi之间的数据进行分组
        int mid=lo+(hi-lo)/2;
        //分别对每一组数据进行排序
        sort(a,lo,mid);
        sort(a,mid+1,hi);
        //再把两个组中的数据进行归并
        merge(a,lo,mid,hi);
    }
    private static void merge(Comparable[]a,int lo,int mid,int hi){
        //定义三个指针
        int i=lo;
        int p1=lo;
        int p2=mid+1;
        //遍历，移动p1指针和p2指针，比较对应索引处得知，找出小的那个，放到辅助数组的对应数组处
        while(p1<=mid && p2<=hi){
            //比较索引处的值
            if(less(a[p1],a[p2])){
                assist[i++]=a[p1++];
            }else {
                assist[i++]=a[p2++];
            }
        }
        //遍历，如果p1的指针没有走完，那么顺序移到p2指针，把对应的元素就放到辅助数组的对应索引处
        while (p1<=mid){
            assist[i++]=a[p1++];
        }
        //遍历，如果p2的指针没有走完，那么顺序移到p1指针，把对应的元素就放到辅助数组的对应索引处
        while (p2<=hi){
            assist[i++]=a[p2++];
        }
        //把辅助数组中的元素拷贝到原数组中
        for (int index = lo; index <=hi ; index++) {
            a[index]=assist[index];
        }
    }

}
